// 最长无重复字符子串
// https://www.lintcode.com/problem/384/


// 法一：哈希表+双指针
class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        int j = 0;
        vector<int> record(256, 0);
        int ans = 0;
        for (int i = 0; i < s.length(); ++i) {
            while (j < s.length() && record[s[j]] == 0) {
                record[s[j++]] = 1;
            }
            ans = max(j - i, ans);
            record[s[i]] = 0;
        }
        return ans;
    }
};

// 法二：哈希表（记录上次出现的位置）+双指针 
class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        int j = 0;
        vector<int> last(256, -1);
        int ans = 0;
        for (int i = 0; i < s.length(); ++i) {
            if (last[s[i]] >= j) {
                j = last[s[i]] + 1;
            }
            ans = max(i - j + 1, ans);
            last[s[i]] = i;
        }
        return ans;
    }
};



class Solution {
public:
    /**
     * @param s: a string
     * @return: an integer
     */
    int lengthOfLongestSubstring(string &s) {
        int l = 0;
        int r = 0;
        int max_len = 1;
        set<char> rec;
        if (s.empty()) return 0;
        while (r < s.length()) {
            if (rec.find(s[r]) == rec.end()) {
                rec.insert(s[r]);
                max_len = max(max_len, r - l + 1);
            } else {
                while (s[l] != s[r]) { 
                    rec.erase(s[l++]);
                }
                l++; 
            }
            r++;
        }
        return max_len;
    }
};